package java_algorithm;

// 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
// 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
// 示例:
// 给定 nums = [2, 7, 11, 15], target = 9
// 因为 nums[0] + nums[1] = 2 + 7 = 9
// 所以返回 [0, 1]

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class demo001 {
    static int[] list = {3,2,4,5,7};
    static int traget = 10;
    private static final String split = "_";


    public static void main(String[] arge) {
        int[] ret = new demo001().twoSum(list,traget);
        System.out.println(ret[0] + "," + ret[1]);
    }


//    public static void main(String[] arge) {
//        String[] ret = typeA();
//        for (String out : ret){
//            System.out.println("目标：" + traget + " 为" + list[Integer.valueOf(out.split(split)[0])] + " + " + list[Integer.valueOf(out.split(split)[1])]);
//        }
//    }
//
//    // 暴力算法
//    private static String[] typeA() {
//        List<String> ret = new ArrayList<>();
//        for (int i = 0; i < list.length; i++) {
//            for (int j = i; j < list.length; j++) {
//                if(list[i] + list[j] == traget) ret.add(i + split +  j);
//            }
//        }
//        return ret.toArray(new String[0]);
//    }
//    public int[] twoSum(int[] nums, int target) {
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i + 1; j < nums.length; j++) {
//                if(nums[i] + nums[j] == target) return new int[]{i,j};
//            }
//        }
//        return null;
//    }

    /**
     * 方法二：两遍哈希表
     */
//    public int[] twoSum(int[] nums, int target) {
//        Map<Integer, Integer> map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            map.put(nums[i], i);
//        }
//        for (int i = 0; i < nums.length; i++) {
//            int complement = target - nums[i];
//            if (map.containsKey(complement) && map.get(complement) != i) {
//                return new int[] { i, map.get(complement) };
//            }
//        }
//        throw new IllegalArgumentException("No two sum solution");
//    }
    /**
     * 方法三：一遍哈希表
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

}
